package 笔试.科大讯飞;


import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;

// 叶子节点之间相距为k的叶子节点对对数
//参考1530. 好叶子节点对的数量
public class Demo3 {
    HashMap<TreeNode, LinkedList<Integer>> map;
    int res;

    public int leafPairs(TreeNode root, int k) {
        res = 0;
        map = new HashMap<>();
        dfs(root, k);
        return res;

    }

    public LinkedList<Integer> dfs(TreeNode cur, int k) {
        if (cur == null) return new LinkedList<>();//长度为0
        if (cur.left == null && cur.right == null) {//叶子节点的list长度为1
            LinkedList<Integer> list = new LinkedList<>();
            list.add(1);
            return list;//List长度为1
        }
        LinkedList<Integer> list0 = dfs(cur.left, k);//代表叶子节点数,叶子节点的节点数
        LinkedList<Integer> list1 = dfs(cur.right, k);
        LinkedList<Integer> myList = new LinkedList<>();
        myList.add(0);//当前节点不是叶子节点.

        //left.get(a)*right.get(b) where k = a+b+2;
        //对于任意的节点P，我们先通过递归的方式，统计叶子节点与 P的左孩子left、右孩子right 之间的距离；
        // 这样，两个以 P 为最近公共祖先的叶子节点 A、B，其中一个（例如 A）在以left 为根的子树中，另一个（例如 B）在以right 为根的子树中。
        // A 与 B 之间的距离，就等于 A 与 left 之间的距离，加上 B 与 right之间的距离，再加上 2。
        for (int x = 0; k - x - 2 >= 0; x++) {
            int y = k - x - 2;
            int ans0 = list0.size() > x ? list0.get(x) : 0;
            int ans1 = list1.size() > y ? list1.get(y) : 0;
            res += (ans0 * ans1);
        }

        Iterator<Integer> itr0 = list0.iterator();
        Iterator<Integer> itr1 = list1.iterator();
        while (true) {
            if (!itr0.hasNext() && !itr1.hasNext()) break;
            int c = itr0.hasNext() ? itr0.next() : 0;
            int d = itr1.hasNext() ? itr1.next() : 0;
            myList.add(c + d);
        }
        return myList;

    }
}
